package ljl.alg.wangzheng_camp.round1.hashmap;

import java.util.HashMap;
import java.util.Map;

/**
 * 哇哦
 * 我第一次独立做出来这道题
 * */
public class _146_lru {
    
    /*
     * 这个得自定义链表因为 java 的 linkedlist 的 node 没法操作
     *
     * 首先这是个缓存，也就是个 kv 存储，简称 map
     * 所以 key 是唯一的，需要一个 hashmap；值不能是简单的 value，因为值会移动！
     *
     * 思路：
     * 1. put 时如果存在了，挪到最前面；不存在，直接放到最前面
     *   如果数量超了，删掉尾部
     * 2. get 时，挪到最前面
     *
     * 就这两点吧！
     *
     * */
    class LRUCache2 {
        
        static class Node {
            int key, value;
            Node prev, next;
        }
        
        Map<Integer, Node> nodes = new HashMap<>();
        Node head, tail;
        int cap;
        int size;
        
        public LRUCache2(int capacity) {
            this.cap = capacity;
        }
        
        public int get(int key) {
            if (!nodes.containsKey(key)) return -1;
            Node node = nodes.get(key);
            moveToHead(node);
            return node.value;
        }
        
        public void put(int key, int value) {
            
            if (nodes.containsKey(key)) {
                Node old = nodes.get(key);
                old.value = value;
                moveToHead(old);
                return;
            }
            
            size++;
            Node node = new Node();
            node.key = key;
            node.value = value;
            nodes.put(key, node);
            
            if (nodes.size() == 1) {
                head = tail = node;
            } else {
                head.prev = node;
                node.next = head;
                head = node;
                
                if (size > cap) {
                    Node last = tail;
                    nodes.remove(last.key);
                    
                    tail = last.prev;
                    last.prev = null;
                    tail.next = null;
                    
                    size--;
                }
            }
        }
        
        void moveToHead(Node node) {
            if (node != head) {
                Node prev = node.prev;
                prev.next = node.next;
                if (node != tail)
                    node.next.prev = prev;
                else
                    tail = prev;
                
                head.prev = node;
                node.next = head;
                node.prev = null;
                
                head = node;
            }
        }
    }
    
    /*
    * 还有个解法，是使用两个 sentinel 节点，head 和 tail
    * 节约了一些边界判断，我看了看，有几处确实可以省去，还蛮不错的，试试？
    *
    * 大差不差
    *
    * */
    
    class LRUCache {
        
        static class Node {
            int key, value;
            Node prev, next;
        }
        
        Map<Integer, Node> nodes = new HashMap<>();
        Node head = new Node(), tail = new Node();
        int cap;
        int size;
        
        public LRUCache(int capacity) {
            this.cap = capacity;
            head.next = tail;
            tail.prev = head;
        }
        
        public int get(int key) {
            if (!nodes.containsKey(key)) return -1;
            Node node = nodes.get(key);
            moveToHead(node);
            return node.value;
        }
        
        public void put(int key, int value) {
            
            if (nodes.containsKey(key)) {
                Node node = nodes.get(key);
                node.value = value;
                moveToHead(node);
                return;
            }
            
            size++;
            Node node = new Node();
            node.key = key;
            node.value = value;
            nodes.put(key, node);
            
            add(node);
            
            if (size > cap) {
                size--;
                nodes.remove(remove(tail.prev).key);
            }
        }
        
        void moveToHead(Node node) {
            remove(node);
            add(node);
        }
        void add(Node node) {
            Node headNext = head.next;
            
            headNext.prev = node;
            node.next = headNext;
            
            head.next = node;
            node.prev = head;
        }
        
        Node remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            return node;
        }
    }
    
}
